1. Field of the Invention
The present invention generally relates to keyboards, typewriters, or data entry devices. More particularly, this invention pertains to methods and apparatuses for generating characters, or character signals, or other input signals to data processing or communications systems by actuating one or more keys.
2. Description of the Related Art
Data-processing devices such as digital computers use internal character sets to represent data or to communicate with other devices. These character sets, or code pages as is sometimes known, contain letters in natural languages as well as some additional characters such as numbers and punctuation symbols (and other “non-printable” characters, etc.). A character set corresponding to a European language typically consists of order of 100 to 200 characters (e.g., letters, symbols, etc.). Character sets corresponding to some languages such as Chinese, Korean, and Japanese, however, contain thousands of characters or more. A standard character set known as Unicode can represent millions of characters from (virtually) all known country- and language-specific character sets. In some cases, different character sets (and/or encoding schemes, etc.) are used for different purposes, for example, for internal use, for transmitting data, and so forth.
A user typically enters data or other input signals (e.g., sequences of characters) using a keyboard or keypad device that includes keys or buttons for entering individual characters or for modifying typed characters, etc. For entering English alphabets on data processing systems such as personal computers (PCs), most keyboards use about 100 keys arranged in a well known “QWERTY” layout. Most keys in commonly used keyboards typically have a one-to-one mapping (or, one-to-few mapping, when modifier keys are used, etc.) to characters from (a subset of) the internal character set. For example, a single key is assigned to a single alphabet (lower-case and upper-case) in many English keyboards. Another popular device for inputting alphabets is a numeric keypad having at least 12 keys, numbers 0 through 9 and * and #. The numeric keypad was originally designed to key in telephone numbers. But, due to recent technological advances, especially in the areas of data communications, this keypad design has been widely used for inputting other letters or symbols in many mobile devices. In the so-called Multi-Tap mode, for example, English alphabets are generated by pressing appropriate numerical keys for a predetermined number of times, usually one to three times.
As the size of a keyboard or keypad (or, the device on which the keypad is disposed) decreases, and hence, as the ratio between the number of characters to be represented/encoded and the number of keys available on the keypad increases, it becomes more difficult to represent characters in an efficient way. For a mobile device, additional challenges are, among other things, (1) the device's form factor (or, the keypad's size) is relatively small and each key has to be much smaller than its counterpart in bigger devices or bigger keyboards, and (2) the user might not be able to use all fingers, or even two hands, under many circumstances where the device is typically used. For most small mobile phones, English alphanumeric characters are typically entered by the user using only one or few fingers or thumbs. It is, therefore, considered desirable to have the ability to efficiently input (a certain subset of) alphabetic letters or symbols (or, other input signals, such as control characters, navigation signals, etc.) into a device which is too small, or otherwise too inconvenient, to permit use of (a portion of) a “full-size” keyboard (e.g., keyboard possessing full-size keys with each key dedicated to one or two letters, etc.).
In order to facilitate inputting more characters than would be possible on a small (conventional) keyboard, various methods of using multiple keys (or, multiple key presses or keystrokes), in a sequential fashion, to represent a single letter have been developed, including the aforementioned Multi-Tap mode. These methods generally fall into the following three categories (or, certain combinations of the three): (1) Using a “prefix”. A prefix key is not considered a character, and a character is parsed based on the prefix and the subsequently typed one or more keys. One of the most popular variants of these prefix keys are those modifier keys such as Shift, Ctrl, or Alt keys typically found on PC keyboards, which modify the generated signal of a key (e.g., when pressed together with the key, etc.). A prefix can be a sequence of one or more predetermined keystrokes. (2) Using a fixed predetermined number of keys to represent a character. Character is parsed based on the set of keys as a whole. This facilitates easy parsing since the character code needs to be generated only when the preset number of keystrokes are observed/received. This is sometimes known as fixed-length encoding in the field of data communications. (3) Using a special marker to denote character boundaries. For example, pressing a special key (or, postfix key) or pausing for a predetermined time interval marks the end of a character and beginning of a new character. The multi-tap mode, for example, uses a pause of 0.5 or 1.0 second to demarcate the boundaries between the characters which use the same keys. This forced pause is one of the main limitations of the multi-tap mode: The typing speed is inherently limited by the pauses between the characters.
Morse code used in radio communications may be viewed as a sequential keystroke coding scheme. Morse code uses one key, or more precisely, two signals, a “dot” and a “dash”, and various lengths of pauses or gaps. Different intervals of pauses are used to separate key signals, characters, words, and sentences, etc. Morse code essentially belongs to the category (3) mentioned above if we view a telegraphy device as a two-key keypad, one for a dot and the other for a dash. (It should be noted, however, that a telegraphy device is not considered a keyboard (in general or in the pertinent arts, etc.) and that this analogy should not be taken too literally.) To illustrate the importance of the pauses or character boundary markers, FIGS. 1A-1D show the same sequences of a dot 1104 and two dashes, 1106 and 1108, with different intervals or gaps between them. These sequences are depicted against an arbitrary linear time axis 1102, which has appropriate marks in each figure. FIG. 1A shows a letter, ‘w’, FIG. 1B shows ‘a’ followed by ‘t’, FIG. 1C shows ‘e’ followed by ‘m’, and FIG. 1D shows a sequence of three characters, ‘e’, ‘t’, and ‘t’, according to the International Morse Code.
Certain embodiments of the present invention utilize another type of mapping between sequential keystrokes and characters based on the so-called prefix-free encoding. A prefix-free code is a code constructed so that dividing the code word (e.g., corresponding to a single letter) into two pieces cannot result in the first being a code word, and it is typically used in electronic communications and, in particular, for data compression. The basic idea of some embodiments of the present invention is that we view the character-keystroke mapping as an encoding of characters using the available keys on a keyboard (e.g., using a particular encoding scheme, etc.). Then the design of a keyboard (or, keyboard layout) becomes the problem of finding an (optimal, near-optimal, or otherwise efficient) encoding scheme for the given character set with the available keys.
At least one embodiment of the present invention teaches how to systematically design or configure efficient and/or optimal keyboards based on prefix-free encoding utilizing the information regarding the character occurrence frequencies. It is well recognized that not all letters/symbols in a character system occur with the same (average) frequency in a typical written (or, colloquial) text. In the modern English language, for example, letter E occurs most frequently (about 13% of the times) among 26 alphabets, and letter Z appears least frequently (about 0.1% of the time). In general, the most frequently used character/symbol in any written language is a space. Most keyboards and data-entry devices and methods, however, do not take this fact into account and there is no or little correlation between the frequency of occurrence of characters and the key arrangement or the like. (Most notable exception may be the “huge” spacebar key found in typical typewriters or computer keyboards, which can often be pressed with a thumb of either hand. Also, certain frequently used keys such as Enter or Shift tend to have slightly bigger sizes than other keys.) For example, the “QWERTY” keyboard was developed in the early days of mechanical typewriters, mainly to minimize mechanical jamming instances associated with typing English letters. Accordingly, the inefficient arrangement of the letters on the keys leads to longer data entry time. (It should noted, however, that a certain group of letters (e.g., lower-case alphabets) are easier to type (e.g., a single keystroke) than other group of letters (e.g., certain symbols) which require activation of more than one key. This design reflects the fact that lower-case alphabets overall occur more frequently than other symbols.) This problem is more pronounced for smaller devices, where more than one keystrokes may be required for inputting a character. Most widely used typing schemes on a numerical keypad or 12-digit phone keyboard (e.g., using the multi-tap mode, etc.) use a simple key arrangement based on the alphabetical order. This is illustrated in FIG. 1E. The figure shows a keypad 1132 (or, a part of a keypad) where twelve keys 1134 are arranged in a 4 row by 3 column matrix. The keys ‘2’ through ‘9’ are typically used for representing alphabets. The rest four keys are sometimes used for other commonly used symbols such as ‘@’, ‘,’, ‘.’, or a space.
In view of the above limitations, it is an object of at least one embodiment of the present invention to provide an improved method and system for designing efficient and/or optimal keyboards. It is another object of a certain embodiment of the present invention to provide a system for obtaining keyboards or keyboard layouts that are efficient, useful, and easy to learn. It is yet another object of some embodiments of the present invention to provide a system to design/configure keyboards that do not require simultaneous actuation of multiple keys, i.e., simultaneous keystrokes. It is yet another object of certain embodiments of the present invention to provide keyboards/keypads that are more efficient as they are biased on both frequency and alphabetical basis. It is yet another object of certain embodiments of the present invention to provide keyboards providing all or a majority of characters in a character set with less number of keys than the number of characters. It is yet another object of some embodiments of the present invention to provide keyboards that can be effectively operated with one hand or with one or a few fingers or thumbs so that the keyboard is suitable to both handheld devices and other bigger devices which may be effectively operated by people lacking the full use of both hands or all fingers. More specifically, it is an object of certain embodiments of the present invention to provide a system and method to design or configure a keyboard, and a keyboard apparatus of such design or configuration, which has a minimal or near-minimal number of keystrokes per character when averaged over alphabet/letter space in a relevant context or lexical domain, thereby minimizing or reducing the average time to type typical sentences using those keyboards. It is yet another specific object of certain embodiments of the present invention to provide a system and method to design or configure a keyboard, and such a keyboard apparatus thereof, which has minimal or near-minimal learning barrier and requires as little time and effort for a new user to become proficient. It is yet another specific object of certain embodiments of the present invention to provide a system and method to design or configure a keyboard, and such a keyboard apparatus thereof, for which it is easy to figure out the key sequence for a target alphabet or other letter (e.g., based on cues such as key labels, etc.). These and other objects and advantages of the present invention will become apparent from a review of the following specification and accompanying drawings. The foregoing objects are some of but a few of the goals that may be attained by the present invention.